#include "AVLTree.h"  

template<class K, class V>
	int GetHeight(AVLTreeNode<K, V>* node)
	{
		if (node == nullptr)
			return 0;

		int leftHeight = GetHeight(node->_left);
		int rightHeight = GetHeight(node->_right);
		return max(leftHeight, rightHeight) + 1;
	}


	template<class K, class V>
	bool IsBalanced(AVLTreeNode<K, V>* node)
	{
		if (node == nullptr)
			return true;


		int leftHeight = GetHeight(node->_left);
		int rightHeight = GetHeight(node->_right);
		int BF = rightHeight - leftHeight;


		if (BF != node->_bf || abs(BF) > 1)
			return false;


		// 递归检查左右子树
		return IsBalanced(node->_left) && IsBalanced(node->_right);
	}

	template<class K, class V>
	void InOrder(AVLTreeNode<K, V>* node)
	{
		if (node == nullptr)
			return;

		InOrder(node->_left);
		cout << node->_kv.first << " ";
		InOrder(node->_right);
	}

int main()
{
    return 0;
}